import entity.TreeNode;

public class ConvertSortedArrayToBST {
    /*
    * 108. 将有序数组转换为二叉搜索树
    * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
    * 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
    *
    * 1 <= nums.length <= 10^4
    * -10^4 <= nums[i] <= 10^4
    * nums 按 严格递增 顺序排列
    * */
    public static void main(String[] args){

    }

    // 我的想法：递归构造二叉树，要求是平衡树，则将数组从中分割，形成左右子树
    public TreeNode mySolution(int[] nums){
        return build(nums, 0, nums.length);
    }
    // 1.返回节点，便于构造， 传入裁剪后的数组
    // 2.前闭后开，不满足区间定义则返回null
    // 3.构造根节点，裁剪后形成左子树和右子树
    // 过啦！
    public TreeNode build(int[] nums, int Start, int end){
        if (Start >= end)
            return null;
        int index = (Start + end) / 2;
        TreeNode root = new TreeNode(nums[index]);
        root.left = build(nums, Start, index);
        root.right= build(nums, index+1, end);
        return root;
    }
}
